import java.util.Arrays;
import java.util.OptionalInt;
import java.util.stream.IntStream;

public class Solution1011 {
    public int shipWithinDays(int[] weights, int days) {
        int l = Arrays.stream(weights).max().getAsInt();
        int r = Arrays.stream(weights).sum();
        //注意无线循环
        while (l < r) {
            System.out.println(l+":"+r);
            //先试一试中间值
            int cur = (l + r) / 2;
            if (able(weights, days, cur)) {//装得下
                r = cur;
            } else {
                l = cur+1;
            }
            System.out.println(l+":"+r);
        }
        return l;
    }

    //当前的装载量所需的最小天数能不能<=days able:船的装载能力
    public boolean able(int[] weights, int days, int able) {
        int need = 1;//至少要用多少天
        int cout = 0;//累计
        for (int w : weights) {
            if (cout + w > able) {//当下一个加入船舱大于装载能力的时候
                cout = 0;
                need++;
            }
            cout += w;
        }
        return need <= days;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,2,4,1,4};
        int i = new Solution1011().shipWithinDays(arr, 3);
        System.out.println(i);
    }
}
